
#include <algorithm>
#include <chrono>
#include <future>
#include <list>
#include <random>
#include <ratio>
#include <utility>

#include <gflags/gflags.h>
#include <glog/logging.h>

DEFINE_int32(list_size, 10, "list size");

using namespace std::chrono_literals;

template <typename T>
std::list<T> sequential_quick_sort(std::list<T> input)
{
    if (input.empty()) {
        return input;
    }
    std::list<T> result;
    result.splice(result.begin(), input, input.begin());
    T const& pivot = *result.begin();
    auto divide_point = std::partition(input.begin(), input.end(), [&](T const& t) { return t < pivot; });
    std::list<T> lower_part;
    lower_part.splice(lower_part.end(), input, input.begin(), divide_point);
    auto new_lower(sequential_quick_sort(std::move(lower_part)));
    auto new_upper(sequential_quick_sort(std::move(input)));
    result.splice(result.end(), new_upper);
    result.splice(result.begin(), new_lower);
    return result;
}

const size_t ASYNC_THRESHOLD = 100000;
template <typename T>
std::list<T> sequential_quick_sort_async(std::list<T> input)
{
    if (input.empty()) {
        return input;
    }
    std::list<T> result;
    result.splice(result.begin(), input, input.begin());
    T const& pivot = *result.begin();
    auto divide_point = std::partition(input.begin(), input.end(), [&](T const& t) { return t < pivot; });
    std::list<T> lower_part;
    lower_part.splice(lower_part.end(), input, input.begin(), divide_point);
    std::future<std::list<T>> new_lower;
    if (lower_part.size() > ASYNC_THRESHOLD) {
        auto new_lower(std::async(std::launch::async, sequential_quick_sort_async<T>, std::move(lower_part)));
        result.splice(result.begin(), new_lower.get());
    } else {
        auto new_lower(sequential_quick_sort_async(std::move(lower_part)));
        result.splice(result.begin(), new_lower);
    }
    auto new_upper(sequential_quick_sort_async(std::move(input)));
    result.splice(result.end(), new_upper);
    return result;
}

int main(int argc, char* argv[])
{
    gflags::ParseCommandLineFlags(&argc, &argv, true);
    google::SetStderrLogging(google::LogSeverity(FLAGS_minloglevel));
    google::InitGoogleLogging(argv[0]);

    std::random_device rd;
    std::mt19937 gen(rd()); // 梅森旋转随机数引擎
    std::uniform_int_distribution<> dis(1, 100); // 范围 [1, 100]

    std::list<int> my_list;
    for (int i = 0; i < FLAGS_list_size; ++i) {
        my_list.push_back(dis(gen));
    }

    if (FLAGS_list_size < 20) {
        std::ostringstream oss;
        oss << "Random list: ";
        for (auto& x : my_list) {
            oss << x << " ";
        }
        LOG(INFO) << oss.str(); // 一次 log 输出全部内容
    }

    auto t1 = std::chrono::high_resolution_clock::now();
    auto new_list = sequential_quick_sort(my_list);
    auto t2 = std::chrono::high_resolution_clock::now();
    auto elapsed = t2 - t1;
    LOG(INFO) << "Elapsed seconds:       "
              << std::chrono::duration_cast<std::chrono::duration<double, std::ratio<1, 1>>>(elapsed).count()
              << " s\n";

    auto async_t1 = std::chrono::high_resolution_clock::now();
    auto async_new_list = sequential_quick_sort_async(std::move(my_list));
    auto async_t2 = std::chrono::high_resolution_clock::now();
    auto async_elapsed = async_t2 - async_t1;
    LOG(INFO) << "Async Elapsed seconds: "
              << std::chrono::duration_cast<std::chrono::duration<double, std::ratio<1, 1>>>(async_elapsed).count()
              << " s\n";

    if (FLAGS_list_size < 20) {
        std::ostringstream new_oss;
        new_oss << "New list:       ";
        for (auto& x : new_list) {
            new_oss << x << " ";
        }
        LOG(INFO) << new_oss.str(); // 一次 log 输出全部内容
    }

    if (FLAGS_list_size < 20) {
        std::ostringstream new_oss;
        new_oss << "Async new list: ";
        for (auto& x : async_new_list) {
            new_oss << x << " ";
        }
        LOG(INFO) << new_oss.str(); // 一次 log 输出全部内容
    }

    return 0;
}